package Solution176_200;

import java.util.*;

public class Solution181 {
    /**
     * better
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        if(s.length() < 10) return res;
        //储存已经遍历过的子字符串
        Set<String> set1 = new HashSet<>();
        //储存符合条件的子字符串
        Set<String> set2 = new HashSet<>();
        for(int i = 0;i + 10 <= s.length();i++){
            String seq = s.substring(i,i+10);
            if(set1.contains(seq)){
                set2.add(seq);
            }
            set1.add(seq);
        }
        res.addAll(set2);
        return res;
    }

    public List<String> findRepeatedDnaSequences1(String s) {
        int startIndex = 0;
        int endIndex = 10;
        Map<String, Integer> kv = new HashMap<>();
        List<String> result = new ArrayList<>();
        for (; endIndex <= s.length(); endIndex++, startIndex++) {
            String sub = s.substring(startIndex, endIndex);
            if (kv.containsKey(sub)) {
                if (kv.get(sub) == 1) {
                    continue;
                }

                result.add(sub);
                kv.put(sub, kv.get(sub) + 1);
            } else {
                kv.put(sub, 0);
            }
        }
        return result;
    }
}
